package logique.calculateur;

import java.util.LinkedList;

import logique.reseau.Ville;

public class Colonie extends Algorithme {

	/**
	 * <pre>
	 * Paramètre de la fonction d'évaluation des phéromones à laisser sur un chemin.
	 * 
	 * Paramétrage :
	 * 
	 * Les créateurs de l'algorithme de la colonie de fourmis préconisent de donner à 
	 * Q une valeur de l'ordre de la longueur estimée du meilleur chemin. L'idée semble
	 * d'etre d'obtenir des ajouts de phéromones de valeurs comprises entre 0 et 1.
	 * 
	 * Avec ce système, on peut obtenir des pistes augmentant au (grand) maximum de 
	 * nb_fourmis à chaque itération si tant est que le chemin obtenu est aussi bon
	 * que le meilleur chemin estimé. On en déduit que la quantité de phéromones sur
	 * une piste est au maximum (iteration * nb_fourmis) sans tenir compte de l'évaporation.
	 * </pre>
	 */
	public static int Q;
	
	/**
	 * <pre>
	 * Double représentant la vitesse d'évaporation d'une piste de phéromones.
	 * </pre>
	 */
	private static double RO = 0.5;
	
	/**
	 * Utilisée pour limiter les pertes de temps dues aux fourmis égarées. Permet de
	 * borner le chemin parcouru par une fourmi.
	 * 
	 * TODO étudier un controle par distance plutôt que par nombre d'étapes
	 */
	private static int TOLERANCE = 5;
	
	/**
	 * Nombre de passages de la colonie
	 */
	private static int ITERATIONS = 100;
	
	/**
	 * Quantité de phéromones laissées sur le réseau au lancement
	 */
	public static final float TAU = 0.5f;
	
	private static final int MUL_FOURMIS = 5;
	private static final int ANYWHERE = 4;
	private static final int PROP_ETAPES = 3;
	
	
	private LinkedList<Ville> toutesEtapes;
	
	private int nb_etapes;
	private int nb_fourmis;
	
	private Itineraire meilleur_itineraire;

	private int finished;
	
	
	@Override
	public Itineraire calcule() {
		toutesEtapes = new LinkedList<Ville>(prefs.getEtapesObligatoires().getEtapes());
		toutesEtapes.addFirst(prefs.getVilleDepart());
		toutesEtapes.addLast(prefs.getVilleArrivee());
		
		nb_etapes = toutesEtapes.size();
		nb_fourmis = nb_etapes;
		
		/*
		 * prophete true si on utilise un oracle pour initialiser l'algo, 
		 * false sinon
		 *  
		 * taille_max true si on borne les chemins parcourus par les fourmis, 
		 * false sinon
		 * 
		 * start_anywhere true si les fourmis peuvent partir de n'importe où sur 
		 * un chemin acceptable, false si elles ne partent que des origines du chemin
		 * 
		 * evolutionAB true si on fait évoluer ALPHA et BETA d'une itération à l'autre,
		 * false sinon
		 * 
		 */
		boolean prophete = true, taille_max = true, start_anywhere = false, evolutionAB = false;
		
		
		Itineraire chemin_init;
		
		if (prophete){
			
			/* ******************************************
			 * 	  Génération d'un chemin de départ		*
			 ****************************************** */
			getInitialisation().activeVillesVoisines(true);
			chemin_init = getInitialisation().calculeItineraire(calculateur, prefs);
	
			Q = chemin_init.getScore() / 2;
		
			/* ******************************************
			 * 	  	Première piste de phéromones		*
			 ****************************************** */
			
//			for (Troncon t : chemin_init.getTroncons()) {
//				t.getEvaluations().addPheromones(TAU);
//			}
		}
		else{

			chemin_init = new ItineraireVide();
		}
		
		meilleur_itineraire = chemin_init;
		
		int max_etapes = (chemin_init.getLongueur()+1) * TOLERANCE;
		if( max_etapes < 0)
			max_etapes = calculateur.getReseau().getVilles().size()/2;
		
		int max_score = chemin_init.getScore();
		
		/* ******************************************
		 * 		 Initialisation des fourmis			*
		 ****************************************** */
		
		if( getInitialisation().isActiveVillesVoisines() ){
			nb_fourmis = nb_etapes * MUL_FOURMIS;
		}
		Fourmi[] fourmis = new Fourmi[nb_fourmis];
		
		for(int i = 0; i < nb_fourmis; i++){
			if( i < nb_fourmis * ANYWHERE/MUL_FOURMIS)
				fourmis[i] = new Fourmi(this, max_etapes/PROP_ETAPES, taille_max, getInitialisation().getVillesVoisines());
			else
				fourmis[i] = new Fourmi(this, max_etapes, taille_max, start_anywhere);
		}
		
		/* ******************************************
		 * 	  		Lancement des fourmis			*
		 ****************************************** */
	
		// itérations
		int compteur = 0;
		
//		double pas_ALPHA = 1.0 / Math.pow((Math.log10(ALPHA)/Math.log10(5)), 1.0/ITERATIONS);
//		double pas_BETA = 1.0 / Math.pow((Math.log10(BETA)/Math.log10(5)), 1.0/ITERATIONS);
//		
		while(compteur < ITERATIONS){
			
//			if (evolutionAB)
//				evolutionAB(pas_ALPHA, pas_BETA);
		
			if(compteur%5 == 0)
				System.out.println("\t Etape " + compteur);
			
			// toutes les fourmis sont réinitialisées
			finished = 0;
			reinit(fourmis);
			
			for(int i = 0; i < nb_fourmis; i++){

				Thread t  = new Thread(fourmis[i]);
				t.start();
			}

			// On attends que ttes les fourmis aient terminé
			attendreLesAutres();
			
			// Evaporation des phéromones
			evaporation();
			
			compteur++;
		}
		
		return meilleur_itineraire;
	}

	

	
	private void evolutionAB(double pas_ALPHA, double pas_BETA){
		
		/*
		ALPHA -= pas_ALPHA;
		BETA += pas_BETA;
		*/
		
		// TODO écrire une méthode par type (lin, exp, log, evo(?))
//		
//		ALPHA = Math.pow(ALPHA, pas_ALPHA);
//		BETA = Math.pow(BETA, pas_BETA);
	}
	
	private void reinit(Fourmi[] f){
		
		for (int i = 0; i < f.length; i++) {
			f[i].init();
		}
	}
	
	
	private synchronized void evaporation() {
		for (Evaluations eval : calculateur.getEvaluations()) {
			eval.setPheromones(Math.max(new Double(eval.getPheromones()*Math.sqrt(1.0-Colonie.RO)).floatValue(), Float.MIN_VALUE));
		}
		
	}




	@Override
	public Initialisation getInitialisation() {
		// TODO Auto-generated method stub
		if( initialisation == null ){
			// initialisation = new BruteForce();
			initialisation = new NDijkstra();
		}
		return initialisation;
	}




	public LinkedList<Ville> getToutesEtapes() {
		return toutesEtapes;
	}




	public int getNb_etapes() {
		return nb_etapes;
	}




	public synchronized Itineraire getMeilleurItineraire() {
		return meilleur_itineraire;
	}




	public synchronized void setMeilleurItineraire(Itineraire meilleur_itineraire) {
		this.meilleur_itineraire = meilleur_itineraire;
	}
	
	public synchronized int getFinished(){
		return finished;
	}

	public synchronized void incrementeFinished(){
		finished++;
		notifyAll();
	}

	/** Attente non active remplace la boucle while( finished < fourmis.length){ } */
	public synchronized void attendreLesAutres(){
		while(getFinished() < nb_fourmis){
			try{
				wait();
			}
			catch(InterruptedException ie){
				ie.printStackTrace();
			}
		}
	}

}